import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution8 {
    String Serialize(TreeNode root) {
        StringBuilder s = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i<size;i++){
                TreeNode cur = queue.poll();
                if(cur == null){
                    if(s.length() != 0){
                        s.append(",");
                    }
                    s.append("#");
                } else {
                    if(s.length() != 0){
                        s.append(",");
                    }
                    s.append(cur.val);
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
            }
        }
        return new String(s);
    }

    TreeNode Deserialize(String str) {
        TreeNode root = null;
        Queue<TreeNode> queue = new LinkedList<>();
        String[] s = str.split(",");
        if(s.length > 1){
            int val = Integer.parseInt(s[0]);
            root = new TreeNode(val);
            queue.offer(root);
        }
        int index = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i<size;i++){
                TreeNode cur = queue.poll();
                if(cur == null){
                    continue;
                }
                //左
                if(s[index].equals("#")){
                    cur.left = null;
                } else {
                    int val = Integer.parseInt(s[index]);
                    cur.left = new TreeNode(val);
                    queue.offer(cur.left);
                }

                // 右
                index++;
                if(s[index].equals("#")){
                    cur.right = null;
                } else {
                    int val = Integer.parseInt(s[index]);
                    cur.right = new TreeNode(val);
                    queue.offer(cur.right);
                }

                index++;
            }
        }
        return root;
    }
}